package algorithm.disjoint.union;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.union
 * 类 名 称: UnionFindQuickFind
 * 类 描 述: TODO
 * 创建时间: 2020/6/28 10:06 下午
 * 创 建 人: Justice
 */
public class UnionFindQuickFind extends UnionFind {
    public UnionFindQuickFind(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        // 父节点就是根节点
        rangeCheck(v);
        return parents[v];
    }

    @Override
    public void union(int v1, int v2) {
        // 将v1所在集合的所有元素，都嫁接到v2的父节点上
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }
}
